import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-01-10
 * Time: 23:33
 */
public class Solution {
//     思路:
//     先排序
//     排过序之后, 挨个放置, 因为个子低的不会影响个子高的
//     只要放置前预留好正好的空位给 个子>=自身 的人即可
//     注意身高相同的先放置 k 大的, 因为这样k 小的不会首影响
//     相反, 先放 k 小的, k 大的会受影响
    public int[][] reconstructQueue(int[][] people) {
        int len=people.length;
        // 根据身高 升序排序, 相等的话按照 k 降序排序
        // 身高升序的原因: 个子高的看不到个子矮的, 所以数空格时不被前面个子的影响
        //  k 降序的原因: 目的与上面相同, 都是为了数空格时 不受影响
        //    k 大的先放置, 不会出错, 再放 k小的也不会出错
        //  但k小的先放置, k 大的后放置, k 大的会受影响, 会少数空格
        Arrays.sort(people, (a, b)->{
            if(a[0]!=b[0]){
                return a[0]-b[0];
            }else{
                return b[1]-a[1];
            }
        });
        int[][] ans=new int[len][];
        // 挨个放置
        for(int[] arr: people){
            int count=arr[1]; // 这个人的前面应该预留的空格的数目
            for(int i=0;i<len;i++){
                if(ans[i]==null){
                    if(count==0){
                        ans[i]=arr;// 要预留的空格已经足够了 就放置
                        break;
                    }else{
                        // 预留空格
                        count--;// 要预留的空格不够 就继续预留
                    }
                }
            }
        }
        return ans;
    }
}
